package com.zhang.sort.cmp;

import com.zhang.sort.Sort;

/**
 * @author 张吉鑫
 * @Description 插入排序
 * @date 2021/4/12 20:51
 */
public class InsertionSort1 extends Sort {
    /**
     * 执行流程
     * ① 在执行过程中，插入排序会将序列分为2部分
     *   头部是已经排好序的，尾部是待排序的
     * ② 从头开始扫描每一个元素
     *   每当扫描到一个元素，就将它插入到头部合适的位置，使得头部数据依然保持有序
     */
    @Override
    protected void sort() {
        for (int i = 1; i < array.length; i++) {
            int end = i;
            while (end > 0 && (cmp(end,end - 1) < 0)){
                swap(end, --end);
            }
        }
    }
}
